﻿// 3401. 图.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*


给定一个有 n个点，m条边的有向图。

图中第 i个点的价值是 vi，每条边有一个代价 z，不同的边代价可能不一样。

一共有 q个询问，每次询问包含两个数字 u,c
，表示询问一条从 u 点出发的路径，在经过代价总和不超过 c的边的前提下，所能经过的点的价值总和的最大值。

如果一条边被多次经过，那么其代价要计算多次。

如果一个点被多次经过，那么其价值要计算多次。

初始节点的价值也要计算进去。

输入格式
输入的第一行包含三个由空格隔开的正整数 n,m,q。

接下来的一行包括 n 个由空格隔开的非负整数 vi表示编号从小到大所有点的价值。

接下来的 m行每行包含三个由空格隔开的正整数 x,y,z
，表示存在一条从 x到 y代价为 z的有向边。

接下来的 q行每行包含两个由空格隔开的非负整数 u,c。

输出格式
对于每次询问输出一个数，表示相应的答案。

数据范围
1≤n≤2000
,
1≤m≤8000
,
1≤q≤105
,
0≤vi≤104
,
1≤x,y≤n
,
1≤z≤30
,
0≤c≤800
输入样例：
4 4 2
3 2 3 4
1 2 1
2 3 1
3 2 2
3 4 1
2 6
3 2
输出样例：
14
7
样例解释
对于第一个询问最优方案是从 2出发，经过 3,2,3,4四个点，取得的价值是 2+3+2+3+4=14。

对于第二个询问最优方案是从 3出发，经过 4这个点，取得的价值是 3+4=7。
*/
int main()
{
    std::cout << "Hello World!\n";
}

 